package leetcode.code0710;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import leetcode.helper.HelpDebug;

public class Solution {

	Map<Integer, Integer> hash;
	int avl;

	public Solution(int n, int[] blacklist) {
		hash = new HashMap<>();
		init(n, blacklist);
	}

	private void init(int n, int[] blacklist) {
		avl = n - 1;
		Set<Integer> set = new HashSet<>();
		Arrays.sort(blacklist);
		for (int black : blacklist) {
			set.add(black);
		}
		for (int black : blacklist) {
			while (set.contains(avl) && avl > black) {
				avl--;
			}
			if (black == avl) {
				avl--;
				break;
			}
			if (black > avl) {
				break;
			}
			hash.put(black, avl--);
		}
	}

	public int pick() {
		int rdm = (int) (Math.random() * (avl + 1));
		return hash.containsKey(rdm) ? hash.get(rdm) : rdm;
	}

	public static void main(String[] args) {
		Solution so = new Solution(4, HelpDebug.str2array3("[2,1]"));
		for (int i = 0; i < 20; i++) {
			System.out.println(so.pick());
		}

	}

}
